package com.sjc.algorithm.sort;

import java.util.Arrays;

/**
 * 计数排序
 * 数值对号入座，，对应的 数组的下标+1 的值置为1
 * @author by SangJiacun
 * @Date 2020/5/12 16:03
 */
public class CountSort {

    public static void main(String[] args) {
        int[] array = new int[] {92,84,86,85,83,82,88,81,87,99,91,89,90};
        int[] ints = countSortV1(array);
//        int[] ints = countSortV2(array);
        System.out.println(Arrays.toString(ints));
    }

    /**
     * 最大值+1 = 新建数组的长度
     * 如果最小值超过100，至少建立长度=100的数组，浪费空间
     * @param array
     * @return
     */
    private static int[] countSortV1(int[] array){
        // 得到待排序数组的最大值
        int max = array[0];
        for(int i=0;i<array.length;i++){
            if(max < array[i]){
                max = array[i];
            }
        }

        int[] sortArr = new int[max+1];
        for(int i=0;i<array.length;i++){
            sortArr[array[i]] = 1;
        }

        System.out.println(Arrays.toString(sortArr));

        int[] countArr = new int[array.length];
        int index = 0;
        for(int i=sortArr.length-1; i>0; i--){
            if(sortArr[i] == 1){
                countArr[index++] = i;
//                index++;
            }
        }
        return countArr;
    }

    /**
     * 最大值-最小值+1 = 新建数组的长度
     * 如果 最大值，最小值相差太大，也浪费空间。
     * @param array
     * @return
     */
    private static int[] countSortV2(int[] array){
        int max = array[0];
        int min = array[0];
        for(int i=0; i< array.length; i++){
            if(max < array[i]){ max = array[i]; }
            if(min > array[i]){min = array[i]; }
        }

        int[] sortArr = new int[max-min+1];
        for(int i=0; i<array.length; i++){
            sortArr[array[i]-min] = 1;
        }

        // [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
        System.out.println(Arrays.toString(sortArr));

        int[] countArr = new int[array.length];
        int index =0;
        for(int i=sortArr.length-1; i>=0; i--){
            if(sortArr[i] == 1){
                countArr[index] = i+min;
                index++;
            }
        }
        return countArr;
    }
}
